1. Field of the Invention.
This invention relates in general to a data recovery, and more particularly to a majority voting scheme that can arrive at the correct data and resolve ties with a minimum number of reads.
2. Description of Related Art.
There has been a tendency, in digital data systems, to demand a transfer of large amounts of data at high speed. However, it is a common problem in digital data systems for important data to become corrupted by data errors. Data stored on a data storage device, for example, is subject to errors as a result of surface defects or of imperfect tracking between the recording head and a "track" containing the data. Similarly, data that is transmitted from a sender to a receiver on a network may become corrupted by noise. While digital data systems are designed to eliminate sources of errors and to reduce their effects, nevertheless data errors still occur. It is desirable to be able to recover data despite the presence of data errors.
In order to enhance data integrity in digital data systems, such systems commonly employ error correction coding techniques. The use of such techniques enables digital data systems to recover data correctly despite the presence of errors. Using error correction coding, a data system encodes a piece of data into a codeword which typically consists of the original piece of data and some check data. The check data is generated from the original data according to an error-correcting code (ECC). The decoder for the ECC is capable of decoding the codeword to obtain the original data even if some of the data or check symbols are in error. The decoder can distinguish codewords despite errors because the codewords generated by the ECC are sufficiently different from each other.
In magnetic or any other digital recordings, the written data is usually read back as a string of binary bits (alphabets). To ensure data integrity, the user data is usually stored along with ECC (e.g. Reed Solomon) checkbytes. If the read back of the stored data generates a zero ECC syndrome, the data is accepted as correct. In some situations, the ECC syndromes can not be made to be zero and the read back is considered un-recoverable. For an example of an ECC decoder capable of on-the-fly detection of multiple errors and correction of one error per interleave, see commonly owned U.S. Pat. No. 5,329,535, herein incorporated by reference.
The usual digital recording system read back of the stored data can be considered as a special case of the Generalized Majority Voting Data Recovery scheme (GMVDR) where the number of reads is one. In general a GMVDR consists of N-Reads where N can be any positive integer greater than or equal to one. The N-pass majority voting scheme performs N reads of a particular data sector(s) to form an N.times.C accumulation matrix, where C represents, for example, the number of nibbles (or bits). For each column of the matrix, the nibble with the majority forms the output of the majority voting device.
However, N-pass majority voting schemes generally perform all N reads, where N was an odd number greater than or equal to one, to arrive at the correct data and to ensure that there were no ties. Even if the correct data was arrived at after M times, where M is less than N, N-pass majority voting schemes perform all N reads. Thus, all reads in excess of the number of reads necessary to resolve the correct data were superfluous.
It can be seen then that there is a need for a majority voting scheme that can arrive at the correct data and resolve ties with a minimum number of reads.